package Week7;

import java.util.PriorityQueue;
import java.util.Scanner;

public class Day39 {
}

//牛客:神奇的字母（二）
class Main5 {
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int[] hash = new int[26];
        char ret = 0;
        int maxCount = 0;
        while(in.hasNext())
        {
            char[] s = in.next().toCharArray();
            for(char ch : s)
            {
                if(++hash[ch - 'a'] > maxCount)
                {
                    ret = ch;
                    maxCount = hash[ch - 'a'];
                }
            }
        }
        System.out.println(ret);
    }
}

//牛客:MT7 字符编码
class Main6 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            char[] s = in.next().toCharArray();
            // 1. 统计所有字符的频次
            int[] hash = new int[300];
            for(char ch : s) {
                hash[ch]++;
            }
            // 2. 把所有的频次放⼊堆⾥⾯
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for(int i = 0; i < 300; i++) {
                if(hash[i] != 0) {
                    heap.offer(hash[i]);
                }
            }
            // 3. 哈夫曼编码
            int ret = 0;
            while(heap.size() > 1) {
                int t1 = heap.poll();
                int t2 = heap.poll();
                ret += t1 + t2;
                heap.offer(t1 + t2);
            }
            System.out.println(ret);
        }
    }
}

//牛客:DP43 最少的完全平方数
class Main7 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] dp = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            dp[i] = 0x3f3f3f3f;
        }
        dp[0] = 0;
        for(int i = 1; i * i <= n; i++) {
            for(int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}